Morskie opowieści

Limit pamięci: 128 MB

Młody Bajtinson uwielbia przesiadywać w portowej tawernie. Często wysłuchuje tam opowieści o przygodach wilków morskich. Początkowo wierzył we wszystkie, nawet najbardziej nieprawdopodobne zasłyszane historie. Z czasem stał się jednak podejrzliwy. Postanowił napisać program, który będzie sprawdzał, czy usłyszane przez niego opowieści są w ogóle możliwe. Niestety, kiepski z niego programista. Pomóż mu!

Na wodach, po których żeglują marynarze spotykani przez Bajtinsona, znajduje się portów oraz szlaków żeglownych między nimi. Istnienie szlaku żeglownego łączącego dwa porty oznacza, iż możliwe jest wykonanie rejsu, który zaczyna się w jednym z nich, zaś kończy w drugim. Taki rejs jest możliwy w obie strony.

Bajtinson poznał historii morskich przygód. W każdej z nich opisywany marynarz rozpoczynał podróż w jednym z portów, wykonywał pewną liczbę rejsów szlakami żeglownymi i kończył w pewnym, być może tym samym porcie. Bajtinson mógł odbyć wiele rejsów tym samym szlakiem żeglownym, w obu kierunkach.

Wejście

W pierwszym wierszu standardowego wejścia znajdują się trzy liczby całkowite , oraz (, , ). Oznaczają one kolejno: liczbę portów na wodach, po których żeglują marynarze spotkani przez Bajtinsona, liczbę szlaków żeglownych oraz liczbę poznanych opowieści.

Następne wierszy zawiera opis istniejących szlaków żeglownych. Opis pojedynczego szlaku składa się z jednego wiersza zawierającego dwie liczby całkowite oddzielone pojedynczym odstępem, oraz (, ), oznaczające numery portów, które łączy dany szlak.

Kolejne wierszy zawiera opis zasłyszanych przez Bajtinsona przygód. Opis pojedynczej przygody składa się z trzech liczb całkowitych pooddzielanych pojedynczymi odstępami: , oraz (, ). Opis taki oznacza, iż bohater danej przygody rozpoczął ją w porcie o numerze , zakończył w porcie o numerze oraz wykonał w jej trakcie dokładnie rejsów.

W testach wartych łącznie 50% punktów zachodzi dodatkowy warunek .

Wyjście

Twój program powinien wypisać na standardowe wyjście wierszy; -ty wiersz powinien zawierać słowo TAK, jeżeli -ta zasłyszana przygoda (według kolejności z wejścia) była możliwa. W przeciwnym wypadku odpowiedni wiersz powinien zawierać słowo NIE.

Przykład

Dla danych wejściowych:

8 7 4
1 2
2 3
3 4
5 6
6 7
7 8
8 5
2 3 1
1 4 1
5 5 8
1 8 10

poprawną odpowiedzią jest:

TAK
NIE
TAK
NIE

Testy "ocen":

1ocen: , , każdy port połączony z każdym, milion losowych przygód, wszystkie z odpowiedzią TAK;

2ocen: , , rejsy możliwe między portami o numerach o tej samej parzystości, milion losowych przygód, połowa z odpowiedzią TAK, połowa z NIE.

Autor zadania: Wiktor Kuropatwa.